package Medium;

public class LC2336 {
    /**
     * 本质上来说这就是一个堆
     */
    class SmallestInfiniteSet {
        int[] nums = new int[1000];
        int size = 1000;
        boolean[] insetIndicators = new boolean[1000];

        public SmallestInfiniteSet() {
            for (int i = 1; i <= 1000; i++) {
                nums[i - 1] = i;
                insetIndicators[i - 1] = true;
            } // 此时的堆无需调整
        }

        public int popSmallest() {
            if (size <= 0) throw new RuntimeException("Set is empty.");
            int ret = nums[0];
            insetIndicators[ret - 1] = false;
            size -= 1;
            nums[0] = nums[size];
            percolateDown(nums, 0);
            return ret;
        }

        public void addBack(int num) {
            if (insetIndicators[num - 1]) return; // 已经在集合中，不进行任何操作
            insetIndicators[num - 1] = true;
            nums[size++] = num;
            percolateUp(nums, size - 1);
        }

        private void percolateDown(int[] nums, int idx) {
            int cur = idx, n = size;
            while (true) {
                int leftChild = cur * 2 + 1, rightChild = cur * 2 + 2;
                if (leftChild >= n) break;
                int childIdx = -1, childValue = -1;
                if (nums[leftChild] < nums[cur]) {
                    childIdx = leftChild;
                    childValue = nums[leftChild];
                }
                if (rightChild < n && nums[rightChild] < Math.min(nums[cur], nums[leftChild])) {
                    childIdx = rightChild;
                    childValue = nums[rightChild];
                }
                if (childIdx >= 0) {
                    swap(nums, cur, childIdx);
                    cur = childIdx;
                }
                else break;
            }
        }

        private void percolateUp(int[] nums, int idx) {
            int cur = idx;
            while (cur > 0) {
                int parentIdx = (cur - 1) / 2;
                if (nums[parentIdx] > nums[cur]) {
                    swap(nums, parentIdx, cur);
                    cur = parentIdx;
                }
                else break;
            }
        }

        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
}
